package sort;

import java.util.Arrays;

/**
 * 基数排序
 */
public class RadixSort {
    public static void main(String[] args) {
        test(1000000);

    }

    //测试方法
    public static void test(int num){
        int[] arr = new int[num];

        for (int i = 0; i <num ; i++) {
            arr[i] = (int)(Math.random()*8000000);
        }

        long startTime5 = System.currentTimeMillis();
        radixSort(arr);
        long endTime5 = System.currentTimeMillis();
        System.out.println("归并排序花费时间为："+(endTime5-startTime5)+"ms\n");
//        System.out.println(Arrays.toString(arr));

    }

    //基数排序
    public static void radixSort(int[] arr){
        //第一轮（针对每个元素的个位进行处理)

        //定义一个二维数组，表示10个桶，每一个桶就是一个一维数组
        //1、二维数组包含10个一维数组
        //为了防止溢出，每个一维数组大小为arr.length
        //使用空间换时间的算法

        int[][] bucket = new int[10][arr.length];

        //为了记录每个桶中存放了多少个数据，定义一个一维数组来记录每个桶每次放入的数据
        //bucketElementCounts[0]就是记录的bucket[0]这个桶的元素个数
        int[] bucketElementCounts = new int[10];

        //排序的次数和最大数的位数有关
        int max = arr[0]; //假设第一个数最大
        for (int i = 0; i <arr.length ; i++) {
            if(arr[i] > max){
                max = arr[i];
            }
        }
        //得到最大数的位数(利用字符串来求长度)
        int maxLength = (max +"").length();


        for (int i = 0,n = 1; i < maxLength; i++,n *=10) {
            //针对每个元素进行排序
            for (int j = 0; j < arr.length; j++) {
                //取出每个元素的各位
                int digitOfElement = arr[j] /n % 10;
                //放入到对应的桶
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            //将放入桶中的数据依次取出放入原数组
            int index = 0;
            //遍历每一个桶，并将桶中的数据放入原数组
            for (int k = 0; k < bucketElementCounts.length; k++) {
                //判断桶是否有数据
                if (bucketElementCounts[k] != 0) {
                    //循环该桶拿到数据
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        //取出数据放入原数组
                        arr[index] = bucket[k][l];
                        index++;
                    }
                }
                //第i+1轮处理后将bucketElementCounts[k] = 0;
                bucketElementCounts[k] = 0;
            }
        }


    }

}
